برش (نظریه گراف)
در نظریه گراف، یک برش یک افراز از رأس‌های یک گراف در دو مجموعه مجزا می‌باشد. هر برش یک مجموعه-برش ایجاد می‌کند که مجموعه یال‌هایی است که هر راس آن‌ها در یک افراز قرار دارد. در یک شبکه شاره یک برش s-t یک برش است که در آن source و sink باید در مجموعه‌های مجزا باشند و مجموعه-برش آن از یال‌هایی تشکیل شده‌است که از source به سمت sink می‌روند. ظرفیت یک برش s-t برابر مجموع ظرفیت یال‌ها در مجموعه-برش است.[۱]
جستارهای وابسته[ویرایش]
منابع[ویرایش]
- ↑ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001), مقدمه‌ای بر الگوریتم‌ها (2nd ed.), MIT Press and McGraw-Hill, p. 563,655,1043, ISBN 0-262-03293-7.
- مشارکت‌کنندگان ویکی‌پدیا. «Cut (graph theory)». در دانشنامهٔ ویکی‌پدیای انگلیسی، بازبینی‌شده در ۲ ژوئیه ۲۰۱۷.
پیوند به بیرون[ویرایش]
 |
در ویکیانبار پروندههایی دربارهٔ برش (نظریه گراف) موجود است. |